/*
Course Schedule Total Accepted: 9490 Total Submissions: 43774 My Submissions Question Solution
There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

*/

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include <unordered_map>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution1 {
public:
	bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
		
		vector<unordered_set<int>> posts(numCourses);

		for (int i = 0; i < prerequisites.size(); i++)
		{
			posts[prerequisites[i].second].insert(prerequisites[i].first);
				
		}

		//count the preCourses
		vector<int> preNums(numCourses,0);

		for (int i = 0; i < numCourses; i++)
		{
			unordered_set<int> setTemp = posts[i];
			unordered_set<int>::iterator it = setTemp.begin();
			while (it!=setTemp.end())
			{
				preNums[*it]++;
				it++;
			}
		}
		
		//bfs remove a non-pre course each time
		for (size_t i = 0; i < numCourses; i++)
		{
			int j = 0;

			for (; j < numCourses; j++)
			{
				if (preNums[j]==0)
				{
					break;
				}
			}

			if (j == numCourses)
			{
				return false;
			}

			preNums[j] = -1;

			unordered_set<int> setTemp = posts[j];
			unordered_set<int>::iterator it = setTemp.begin();
			while (it != setTemp.end())
			{
				preNums[*it]--;
				it++;
			}


		}


		return true;
	}
};

public class Solution {
	public boolean canFinish(int numCourses, int[][] prerequisites) {
		List<List<Integer>> posts = new ArrayList<List<Integer>>();
		for (int i = 0; i < numCourses; i++) {
			posts.add(new ArrayList<Integer>());
		}

		int[] preNums = new int[numCourses];
		for (int i = 0; i < prerequisites.length; i++) {
			posts.get(prerequisites[i][1]).add(prerequisites[i][0]);
			preNums[prerequisites[i][0]]++;
		}

		Queue<Integer> queue = new LinkedList<Integer>();
		for (int i = 0; i < numCourses; i++) {
			if (preNums[i] == 0){
				queue.offer(i);
			}
		}

		int count = numCourses;
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			for (int i : posts.get(cur)) {
				if (--preNums[i] == 0) {
					queue.offer(i);
				}
			}
			count--;
		}

		return count == 0;
	}
}




/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

int main(int argc, char* argv[])
{

	int num = 2;

	pair<int, int> temp;
	temp.first = 0;
	temp.second = 1;

	vector<pair<int, int>> prere;
	prere.push_back(temp);

	Solution s1;

	if (s1.canFinish(num, prere))
	{
		cout << " Finish." << endl;
	}
	else
	{
		cout << "Cycle." << endl;
	}
	//ifs1.countPrimes(val);

	//strRes = s.findRepeatedDnaSequences(s1);
	//cout << "The result is : " << result << endl;
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;s
/*
//string s1 = "GAGAGAGAGAGA";
string s1 = "GAGAGAGAGAGA";
vector<string> strRes;

TreeNode *root = new TreeNode(1);
TreeNode *left1 = new TreeNode(2);
TreeNode *left2 = new TreeNode(5);

TreeNode *right1 = new TreeNode(3);
TreeNode *right2 = new TreeNode(4);

root->left = left1;
left1->right = left2;

root->right = right1;
right1->right = right2;

//vector<char> level1({ '1', '1', '1', '1', '0' });
//vector<char> level2({ '1', '1', '0', '1', '0' });
//vector<char> level3({ '1', '1', '0', '0', '0' });
//vector<char> level4({ '0', '0', '0', '0', '0' });


vector<vector<char>> grid;
grid.push_back(level1);
grid.push_back(level2);
grid.push_back(level3);
grid.push_back(level4);ss
ListNode *head = new ListNode(1);
ListNode *head1 = new ListNode(2);
ListNode *head2 = new ListNode(6);
ListNode *head3 = new ListNode(3);
ListNode *head4 = new ListNode(4);
ListNode *head5 = new ListNode(5);

ListNode *head6 = new ListNode(6);

head->next = head1;
head1->next = head2;
head2->next = head3;
head3->next = head4;
head4->next = head5;
head5->next = head6;
int val = 6;
*/
